#哈希表，又称散列表

#哈希表类
#一般直接使用元组（列表）、集合、字典来表示

class HashTable:
    '''取余法创建散列表，线性探测法解决冲突（加1法）'''
    def __init__(self,size=10):
        self.size = size
        self.slots = [None] * self.size #槽键
        self.data = [None] * self.size #槽值
    
    def _hash(self, key, size): #取余法
        return (hash(key) & 0x7fffffff) % self.size
    
    def rehash(self, oldhash, size): #加1法
        return (oldhash + 1)%size

    def __setitem__(self, key, data):
        val = self._hash(key, self.size)
        if self.slots[val] == None:
            self.slots[val] = key
            self.data[val] = data
        else:
            if self.slots[val] == key: self.data[val] = data #替换
            else:
                slot = self.rehash(val, self.size)
                while self.slots[slot] and  (self.slots[slot] != key):
                    slot = self.rehash(slot, self.size)
                if self.slots[slot] == None:
                    self.slots[slot] = key
                    self.data[slot] = data
                else: self.data[slot] = data #替换

    def __getitem__(self, key):
        start = self._hash(key, self.size)
        data = None
        stop = False
        found = False
        position = start
        while self.slots[position] and not(found or stop):
            if self.slots[position] == key:
                found = True
                data = self.data[position]
            else:
                position=self.rehash(position, self.size)
                if position == start: stop = True
        return data

H = HashTable(11)
d={54:"cat", 26:"dog", 93:"lion", 17:"tiger", 77:"bird", 
        31:"cow", 44:"goat", 55:"pig", 20:"chicken"}
for i in d: H[i]=d[i]
#print(H.slots,H.data)
print(H[20]) #chicken
H[20] = 'duck'
print(H[20]) #duck
print(H[99]) #None